// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 经典题目：斐波那契数列模型，路径问题

// 技巧：
// dp[] 表多开一个长度，处理数组越界及初始化复杂的问题
// dp[][] 表多开一行，多开一列
// 结合滚动数组优化 - 注意赋值顺序

// 例题 6:
// 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。
// 我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
//
//        骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
//
//        有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
//
//        为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
//
//        返回确保骑士能够拯救到公主所需的最低初始健康点数。
//
//        注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
//
//
//
//        示例 1：
//
//
//        输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
//        输出：7
//        解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
//        示例 2：
//
//        输入：dungeon = [[0]]
//        输出：1
//
//
//        提示：
//
//        m == dungeon.length
//        n == dungeon[i].length
//        1 <= m, n <= 200
//        -1000 <= dungeon[i][j] <= 1000

// 解题思路：
// 解题时如果发现当前的状态是需要依赖后面的状态的，那么就需要定义 dp[i][j] 为从 i,j 出发......
// dp[i][j]: 从 i,j 位置出发，到达右下角的最小血量
// dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j]
// dp[m - 1][n] = 1
// 从下往上填表，每一行从右往左
// 返回 dp[0][0]
// 细节： 当 dp[i][j] <= 0 时，dp[i][j] = 0, 因为骑士的血量不能 <= 0

public class CalculateMinimumHP {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for(int j = 0; j <= n; j++){
            dp[m][j] = Integer.MAX_VALUE;
        }
        for(int i = 0; i <= m; i++){
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m - 1][n] = 1;

        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                if(dp[i][j] <= 0) dp[i][j] = 1;
            }
        }
        return dp[0][0];
    }
}
